1. Field of the Invention
The present invention relates to managing a buffer cache, and more particularly, to managing a buffer cache which uses an extended buffer to perform a page replacement algorithm using information regarding a time at which a page is referred to.
2. Description of the Related Art
Since components included in a digital terminal such as a computer, e.g., a central processing unit (CPU), a memory, a hard disk, a compact disc (CD)-read only memory (CD-ROM), and so forth have different data processing speeds, they cannot operate at the same speed in data input/output operations. Therefore, if an imbalance between the data processing speeds of the components included in the terminal is not corrected, the overall data processing speed of the digital terminal may be reduced.
As a hardware solution to such a problem, a buffer or cache for covering an input/output speed difference between components of the terminal may be used. The buffer or cache reduces the bottlenecks caused by a speed difference between components of the terminal, that is, a phenomenon where a component which processes data at a high speed waits for completion of an operation by a component which processes data at a low speed.
A page replacement policy using a buffer cache for improving a data processing speed has evolved into various algorithms, and many algorithms have been researched to determine whether to maintain a particular page in the buffer cache or move that page down to a hard disk for rapid input/output of the page.
There are various types of page replacement algorithms using a buffer cache, such as Least Recently Used (LRU), 2Q, Early Eviction Least Recently Used (EELRU), Least Recently/Frequency Used (LRFU), Unified Buffer Management (UBM), and the like.
An LRU-K algorithm, one of the page replacement algorithms, determines a block to be replaced, based on reference density estimated from recent K references. That is, a block of which a last kth reference time is oldest among blocks in the buffer cache is replaced. Since the last kth reference time is considered, the LRU-K replacement policy can distinguish frequently referred blocks from infrequently referred blocks, such that blocks which have been recently referred to a small number of times may be preferentially replaced in the buffer cache.
For K=2, to use the LRU-K algorithm, the last reference time of a page and last-preceding reference time information, which is time information immediately preceding the last reference time, are maintained in a header of a buffer, and such reference time information has to be updated each time the page included in the buffer is referred to.
When a particular page is referred to in an auxiliary memory device such as a hard disk and moves up to a main memory device, last reference time information of the particular page is updated, and then when the particular page is referred to in the main memory device again, the last reference time information is recorded as reference time preceding the last reference time and time at which the page was referred to in the main memory device is updated as the last reference time.
When a page replacement policy using a conventional LRU-K algorithm is used, because of limited space in memory, even a page that has been previously referenced may be pushed out of the LRU-K list and recorded in an auxiliary memory device in certain situations. As a result, if such a page is referred to again in a running program, that page has to be read again from the auxiliary memory device, causing additional write/read operations with respect to a disk and thus a delay in data processing time.